package com.dora.algorithm.hsbc;

/*
    An alien mothership is trying to communicate with Earth. lt follows a particular handshake mechanism
    to initiate the conversation. lt sends a stream of numbers to Earth and expects a particular set
    of numbers in return ，to complete the handshake. if the stream contains N numbers, then Earth needs
    to return the top M numbers from the stream,such that those M numbers contain the highest number
    of 1s when represented in their binary form, lf two numbers contain the same number of 1s in their
    binary form, the larger number (in magnitude) should be selected first.

    Design an algorithm that will help carry out this communication.

    Input
    The first line of the input consists of an integer num, representing the number of elements of the
    list sent by the alien mothership (N).
    The second line consists of N space separated integers, representing the elements of the list sent
    by the alien mothership.
    The last line consists of an integer.retM, representing the number of elements of the list returned
    by Earth (M).

    Output
    Print M space separated integers representing the top M numbers returned by Earth.


    Constraints
    0< num ≤ 10^6
    1 <= retM <= num.
    -10^5 <= X <= 10^5, where X represents any number from the stream

    Example
    input
    5
    5 9 8 7 16
    3

    Output:
    7 9 5

    Explanation:
    The Binary form of
    5 is 101
    9 is 1001
    8 is 1000
    7 is 111
    16 is 10000.

    The three numbers that contain the highest number of 1s when represented in their binary form
    are 7, 9 and 5. So, the output is 7, 9, 5.

*/
import java.util.*;

public class AlienShakeHandsSolution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 读取元素个数
        int num = in.nextInt();
        int[] alienList = new int[num];

        // 读取数组元素
        for (int i = 0; i < num; i++) {
            alienList[i] = in.nextInt();
        }

        // 读取 retM
        int retM = in.nextInt();
        in.close();

        // 计算结果
        int[] result = retStream(alienList, retM);

        // 打印输出
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i == result.length - 1 ? "" : " "));
        }
    }

    public static int[] retStream(int[] alienList, int retM) {
        // 将数组转换为列表
        Integer[] arr = Arrays.stream(alienList).boxed().toArray(Integer[]::new);

        // 按照 1 的个数降序排列，若相同按数值大小降序
        Arrays.sort(arr, (a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            return countA == countB ? b - a : countB - countA;
        });

        // 取前 retM 个数并返回
        return Arrays.stream(arr).limit(retM).mapToInt(Integer::intValue).toArray();
    }

    public static int[] retStream1(int[] alienList, int retM) {
        // 转换为列表，方便排序
        List<Integer> list = new ArrayList<>();
        for (int num : alienList) {
            list.add(num);
        }

        // 自定义排序：
        // 1. 先按二进制1的个数降序
        // 2. 如果相同，按数值大小降序
        list.sort((a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            if (countA != countB) {
                return Integer.compare(countB, countA); // 1 的个数降序
            }
            return Integer.compare(b, a); // 数值大小降序
        });

        // 取前 retM 个元素
        int[] result = new int[retM];
        for (int i = 0; i < retM; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}
